package com.ww.springboot.boot.algorithm.leetcode1;

import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

/**
 * 描述：最小基因变化
 *
 * @author 🧑 ‍wanwei
 * @since 2023-05-26 15:13
 */
public class DB433 {

    public static void main(String[] args) {
        String startGene = "AAAAACCC";
        String endGene = "AACCCCCC";
        String[] bank = {"AAAACCCC","AAACCCCC","AACCCCCC"};
        System.out.println(minMutation(startGene, endGene, bank));
    }


    /**
     * 需要进行广度优先遍历 每次都找到变换一次即可得到的下一个字符串 记录后以相同的逻辑继续查找 直到找到或者字符串全部用完为止
     * 查找过程中避免重复查找 即找到过的字符串在下一次不再被使用 不然会陷入无限循环中
     * @param startGene
     * @param endGene
     * @param bank
     * @return
     */
    public static int minMutation(String startGene, String endGene, String[] bank) {
        //层级 即 步数
        int level = 1;
        //避免路径重复
        Set<String> set = new HashSet<>();
        Stack<String> stack = new Stack<>();
        Stack<String> stackNext = new Stack<>();
        stack.push(startGene);
        while (!stack.isEmpty()){
            String pop = stack.pop();
            boolean flag = matchNext(pop,endGene,bank,set,stackNext);
            if(flag){
                return level;
            }
            if(stack.isEmpty()){
                stack = stackNext;
                stackNext = new Stack<>();
                level++;
            }
        }





        return -1;
    }

    /**
     * 匹配下一层次的字符串
     *
     * @param startGene
     * @param bank
     * @param oldSet
     */
    private static boolean matchNext(String startGene,String endGene, String[] bank, Set<String> oldSet,Stack<String> stack){
        for (String s : bank) {
            if(oldSet.contains(s)){
                continue;
            }
            //比较字符串之间的差别是否为1
            boolean b = compareStr(s, startGene);
            if(b){
                if(s.equals(endGene)){
                    return true;
                }
                oldSet.add(s);
                stack.push(s);
            }
        }
        return false;
    }

    private static boolean compareStr(String s, String startGene) {
        int time = 0;
        for (int i = 0; i < s.length(); i++) {
            if(s.charAt(i) != startGene.charAt(i)){
                time++;
            }
            if(time > 1){
                return false;
            }
        }
        return true;
    }


}
